package a2022.a20220526;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lenovo
 * @date 2022/5/26
 */
public class a {
//positions = [[1,2],[2,3],[6,1]]
    // 第一个 从 1开始算起 宽度是2
    // 第二个 从2算起 宽度是3
    // 第三个 从6算起 宽度是1
    public List<Integer> fallingSquares(int[][] positions) {
        int length = positions.length;
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            int left1 =  positions[i][0];
            int right1 = positions[i][0] + positions[i][1] - 1;
            int hgt = positions[i][1];
            for (int j = 0; j < i; j++) {
                int left2 =  positions[j][0];
                int right2 = positions[j][0] + positions[j][1] - 1;
                if (right1 >= left2 && right2 >= left1)
                    hgt = Math.max(hgt, list.get(j) + positions[i][1]);
            }
            list.add(hgt);
        }
        for (int i = 1; i < length; i++) {
            list.set(i, Math.max(list.get(i), list.get(i - 1)));
        }
        return list;
    }
//    public List<Integer> fallingSquares(int[][] positions) {
//        int n = positions.length;
//        List<Integer> heights = new ArrayList<Integer>();
//        for (int i = 0; i < n; i++) {
//            int left1 = positions[i][0], right1 = positions[i][0] + positions[i][1] - 1;
//            int height = positions[i][1];
//            for (int j = 0; j < i; j++) {
//                int left2 = positions[j][0], right2 = positions[j][0] + positions[j][1] - 1;
//                if (right1 >= left2 && right2 >= left1) {
//                    height = Math.max(height, heights.get(j) + positions[i][1]);
//                }
//            }
//            heights.add(height);
//        }
//        for (int i = 1; i < n; i++) {
//            heights.set(i, Math.max(heights.get(i), heights.get(i - 1)));
//        }
//        return heights;
//    }

}
